<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>mergeSort</title>
</head>

<body>
    <script>
        function mergeSort(arr) { //采用自上而下的递归方法
            var len = arr.length;
            if (len < 2) {
                return arr;
            }
            var middle = Math.floor(len / 2),
                left = arr.slice(0, middle),
                right = arr.slice(middle);
            return merge(mergeSort(left), mergeSort(right)); //分
        }

        function merge(left, right) { //治
            var result = [];

            while (left.length && right.length) {
                if (left[0] <= right[0]) {
                    result.push(left.shift());
                } else {
                    result.push(right.shift());
                }
            }

            while (left.length)
                result.push(left.shift());

            while (right.length)
                result.push(right.shift());

            return result;
        }
        console.log(mergeSort([9, 55, 4, 1, -2, 8]))
    </script>
</body>

</html>